package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 19. 删除链表的倒数第 N 个结点
 * @since 2024/2/2 14:03
 */
public class RemoveNthFromEnd19 {
    // 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 哨兵模式，防止递归删除倒数第一个节点出现问题
        ListNode sentinel = new ListNode(-1, head);
        if (n % 2 == 0) {
            recur(sentinel, n);
        } else {
            remove(sentinel, n);
        }

        return sentinel.next;
    }

    // 方法1：递归，排名法
    private static int recur(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        // 获取下一个节点的排名
        int nth = recur(p.next, n);
        if (nth == n) {
            // 如果下一个节点的排名就是要删除的，删除下一个节点
            p.next = p.next.next;
        }
        return nth + 1; // 放当前节点排名
    }

    // 方法2：循环双指针
    private static void remove(ListNode sentinel, int n) {
        ListNode p1 = sentinel;
        ListNode p2 = sentinel;

        // 让p2走n+1步
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }

        // 此时p2和p1距离相隔n个距离，然后循环，移动双指针，直到p2=null;
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        // 此时p1指向了待删除节点前驱
        p1.next = p1.next.next;
    }
}
